package com.datastructures.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找
 * @author MaoLin Wang
 * @date 2019/10/3112:54
 */
public class BinarySearch {
    public static int count=0;

    public static void main(String[] args) {
        //必须是有序的
        int arr[]={2,5,7,8,10,22,22};
       // int arr[]=new int[100];
      //  for (int i=0;i<100;i++){
        //    arr[i]=i;
       // }
        List<Integer> list = binarySearch(arr, 0, arr.length-1, 2);
        System.out.println(list);
        System.out.println(count);
    }

    public static List<Integer> binarySearch(int[]arr, int left, int right, int value){

        count+=1;
        //当left>right时，说明完成整个数组的递归，仍然没有找到，结束递归
        if (left>=right){
            return new ArrayList<Integer>();
        }
        int mid=(left+right)/2;
        int midVal=arr[mid];

        if (value>midVal){//向右递归
            return binarySearch(arr,mid+1,right,value);

        }else if (value<midVal){
            return binarySearch(arr,left,mid-1,value);
        }else {
            //找到mid值，向mid左边扫描，将所有满足满足value的元素下标加到集合中
            List<Integer>list=new ArrayList<Integer>();
            int temp = mid -1;
            while (true){
                if (temp<0 || arr[temp] !=value){
                    break;
                }
                //放入集合
                list.add(temp);
                temp-=1;
            }
            list.add(mid);
            //同样道理向右扫描
             temp = mid +1;

            while (true){
                if (temp>arr.length-1 || arr[temp] !=value){
                    break;
                }
                //放入集合
                list.add(temp);
                temp+=1;
            }

            return list;
        }
    }
}
